package chapter02;

public class RecoverTree99 {
    /**
     * 中序遍历
     * 中序遍历树 保存需要交换的节点 结束后交换两个节点
     * first second:保存需要交换的第一和第二个节点  pre:遍历x之前的节点
     * process(x) 当前节点x 与节点pre比较 必须满足节点前小后大 若不满足找到了需要交换的节点
     * 3 [15 8] 10 [13 5] 16 情况一
     *   fi            se
     * [5 3] 8 10 13 15 16   情况二
     * fi se
     * 递归出口
     *  1).x==null
     *    return
     *  2).中序递归遍历 更新first second pre
     *     a).pre!=null&&pre.val>=x.val&&first==null 找到第一对前大后小 为了兼容第二种情况second同时更新
     *        first=pre
     *        second=x
     *     b).pre!=null&&pre.val>=x.val&&second!=null 已经找到过一对前大后小 这是第二对 更新second
     *        second=x
     *     c).更新pre
     *        pre=x
     */
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public TreeNode pre;
    public TreeNode firstNode;
    public TreeNode secondNode;

    public void recoverTree(TreeNode root) {
        if(root==null){
            return;
        }
        process(root);
        int temp=firstNode.val;
        firstNode.val=secondNode.val;
        secondNode.val=temp;
    }

    public void process(TreeNode x){
        if(x==null){
            return;
        }
        process(x.left);
        if(pre!=null&&pre.val>=x.val&&firstNode==null){
            firstNode=pre;
            secondNode=x;
        }
        if(pre!=null&&pre.val>=x.val&&secondNode!=null){
            secondNode=x;
        }
        pre=x;
        process(x.right);
    }
}
